#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <stdbool.h>
#include <errno.h>

/* This program gives whether two points on a circuit board are already
 * connected. i.e. there is a path between them. If they're not connected, we
 * assume that a connection is then made and modify the internal state to
 * reflect that.
 *
 * The data structure we employ is a list of lists. Each sublist contains the
 * elements that are connected together.
 *
 * E.g. On a board where there exists connections between 1, 2, 3 and 4, 5, 6
 * we would have
 *
 * []-> 1, 2, 3
 * []-> 4, 5, 6
 *
 * If we now make a connection between 2 and 5 we then get
 * []-> 1, 2, 3, 4, 5, 6
 *
 * because all the points are connected now.
 *
 * This is O(n) because the total of all elements in all lists is n and we look
 * at an element only once.
 */

struct node {
	struct node *next;
	int val;
};

struct lnode {
	struct lnode *next;
	struct node *list;
	struct node *last; /* Optimization for merging lists */
};

struct lnode lhead = { NULL, NULL };

struct node *alloc_node(int val)
{
	struct node *ptr = malloc(sizeof(*ptr));

	if (!ptr)
		return NULL;

	ptr->val = val;
	ptr->next = NULL;

	return ptr;
}

struct lnode *alloc_lnode(void)
{
	struct lnode *ptr = malloc(sizeof(*ptr));

	if (!ptr)
		return NULL;

	ptr->next = NULL;
	ptr->list = NULL;

	return ptr;
}

/* I don't know if goto is controversial with your codebase. In the kernel this
 * is accepted method for nested error handling
 */
int create_new_list(int p, int q)
{
	struct node *pnode, *qnode;
	struct lnode *lp;

	pnode = alloc_node(p);
	if (!pnode)
		return -ENOMEM;

	qnode = alloc_node(q);
	if (!qnode)
		goto freep;

	lp = alloc_lnode();
	if (!lp)
		goto freeq;

	/* Link the two nodes. Set the last ptr */
	lp->last = qnode;
	pnode->next = qnode;
	lp->list = pnode;

	/* Insert new lnode into the super list */
	lp->next = lhead.next;
	lhead.next = lp;

	return 0;

freeq:
	free(qnode);

freep:
	free(pnode);

	return -ENOMEM;
}

void delete_lnode(struct lnode *l)
{
	struct lnode *p1 = lhead.next, *p2 = &lhead;

	/* Traverse super list and unlink the lnode. Can be optimized to
	 * constant time if we use a doubly linked list
	 */
	while (p1 != l) {
		assert(!p1);

		p2 = p1;
		p1 = p1->next;
	}

	p2->next = p1->next;
	free(p1);
}

void merge_lnodes(struct lnode *l1, struct lnode *l2)
{
	l1->last->next = l2->list;
	l1->last = l2->last;
	delete_lnode(l2);
}

bool exists(struct node *list, int p)
{
	struct node *ptr = list;

	while (ptr) {
		if (ptr->val == p)
			return true;

		ptr = ptr->next;
	}

	return false;
}

struct lnode *find_list(int p)
{
	struct lnode *l = lhead.next;

	while (l) {
		if (exists(l->list, p))
			return l;

		l = l->next;
	}

	return NULL;
}

void insert(struct lnode *l, int p)
{
	struct node *ptr = alloc_node(p);

	if (!ptr)
		return;

	ptr->next = l->list;
	l->list = ptr;
}

int is_connected(int p, int q)
{
	int rc = 0;

	struct lnode *plist = find_list(p);
	struct lnode *qlist = find_list(q);

	if (!plist && !qlist) /* both new, only connected to each other */
		create_new_list(p, q);
	else if (plist == qlist) /* they are already connected */
		rc = 1;
	else if (plist && qlist) /* both were disjoint, now connected */
		merge_lnodes(plist, qlist);
	else if (plist) /* q is new. add to p's set */
		insert(plist, q);
	else if (qlist) /* p is new, add to q's set */
		insert(qlist, p);
	else
		assert(0);

	return rc;
}

void print_sets(void)
{
	struct lnode *l = lhead.next;
	int i = 0;

	while (l) {
		struct node *ptr = l->list;
		printf("%d: ", i++);

		while (ptr) {
			printf("%d ", ptr->val);
			ptr = ptr->next;
		}
		printf("\n");

		l = l->next;
	}
	printf("\n");
}

int main(void)
{
	printf("2, 3 - %d\n", is_connected(2, 3));
	print_sets();
	printf("1, 3 - %d\n", is_connected(1, 3));
	print_sets();
	printf("1, 2 - %d\n", is_connected(1, 2));
	print_sets();
	printf("4, 5 - %d\n", is_connected(4, 5));
	print_sets();
	printf("5, 6 - %d\n", is_connected(5, 6));
	print_sets();
	printf("6, 7 - %d\n", is_connected(6, 7));
	print_sets();
	printf("1, 7 - %d\n", is_connected(1, 7));
	print_sets();
	printf("1, 5 - %d\n", is_connected(1, 5));
	print_sets();

	/* TODO: Free memory for lists for completeness. */
	return 0;
}



